35C - Fire Again - CodeForces Solution


brute force dfs and similar shortest paths *1500

Please click on ads to support us..

C++ Code:

#include <bits/stdc++.h>
using namespace std;
const int N=3000;
int n,m,k,mxlvl=-1;
pair<int,int>nodee;
int dx[4] {0,-1,0,1};
int dy[4] {-1,0,1,0};
vector<int>adj[N];
int ans[N][N];
vector<pair<int,int>>pushat;
bool is_vlaid(int i,int j){
    return i >= 1 && i <= n && j >= 1 && j <= m && ans[i][j] == -1;
}
void bfs(){
    queue<pair<int,int>>q;
    for(auto node:pushat)
        ans[node.first][node.second]=0,q.push(node),nodee=node;
    for (int i = 0; q.size(); ++i) {
        int sz=q.size();
        while (sz--){
            for(int j=0;j<4;j++){
                pair<int,int>qso=q.front();
                qso.first+=dx[j],qso.second+=dy[j];
                if(is_vlaid(qso.first,qso.second)){
                    nodee=qso;
//                    nodee.first+=1,nodee.second;
                    ans[qso.first][qso.second]=i+1;
                    q.push(qso);
                }
            }
            q.pop();
        }
    }
}
int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin>>n>>m>>k;
    pushat.resize(k);
    for (int i = 0; i < k; ++i) {
        int u,v;cin>>u>>v;
        pushat.push_back({u,v});
    }
    ::memset(ans,-1, sizeof ans);
    bfs();
    cout<<nodee.first<<' '<<nodee.second;
    return 0;
}


Comments

Submit
0 Comments
More Questions

320A - Magic Numbers
1658A - Marin and Photoshoot
514A - Chewbaсca and Number
382A - Ksenia and Pan Scales
734B - Anton and Digits
1080A - Petya and Origami
1642D - Repetitions Decoding
1440A - Buy the String
1658F - Juju and Binary String
478A - Initial Bet
981A - Antipalindrome
365A - Good Number
1204B - Mislove Has Lost an Array
1409D - Decrease the Sum of Digits
1476E - Pattern Matching
1107A - Digits Sequence Dividing
1348A - Phoenix and Balance
1343B - Balanced Array
1186A - Vus the Cossack and a Contest
1494A - ABC String
1606A - AB Balance
1658C - Shinju and the Lost Permutation
1547C - Pair Programming
550A - Two Substrings
797B - Odd sum
1093A - Dice Rolling
1360B - Honest Coach
1399C - Boats Competition
1609C - Complex Market Analysis
1657E - Star MST